{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Maximal Itemsets via the FP-Max Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function implementing FP-Max to extract maximal itemsets for association rule mining"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> from mlxtend.frequent_patterns import fpmax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Apriori algorithm](./apriori.md) is among the first and most popular algorithms for frequent itemset generation (frequent itemsets are then used for association rule mining). However, the runtime of Apriori can be quite small, especially for datasets with a large number of unique items, as the runtime grows exponentially depending on the number of unique items. \n",
    "\n",
    "In contrast to Apriori, [FP-Growth](./fpgrowth.md) is a frequent pattern generation algorithm that inserts items into a pattern search tree, which allows it to have a linear increase in runtime with respect to the number of unique items or entries.\n",
    "\n",
    "FP-Max is a variant of FP-Growth, which focuses on obtaining maximal itemsets.\n",
    "**An itemset X is said to maximal if X is frequent and there exists no frequent super-pattern containing X.** In other words, a frequent pattern X cannot be sub-pattern of larger frequent pattern to qualify for the definition *maximal itemset*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "- [1] Grahne, G., & Zhu, J. (2003, November). Efficiently using prefix-trees in mining frequent itemsets. In FIMI (Vol. 90).\n",
    "\n",
    "## Related\n",
    "\n",
    "- [FP-Growth](./fpgrowth.md)\n",
    "- [Apriori](./apriori.md)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 1 -- Maximal Itemsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `fpmax` function expects data in a one-hot encoded pandas DataFrame.\n",
    "Suppose we have the following transaction data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],\n",
    "           ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],\n",
    "           ['Milk', 'Apple', 'Kidney Beans', 'Eggs'],\n",
    "           ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'],\n",
    "           ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can transform it into the right format via the `TransactionEncoder` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Apple</th>\n",
       "      <th>Corn</th>\n",
       "      <th>Dill</th>\n",
       "      <th>Eggs</th>\n",
       "      <th>Ice cream</th>\n",
       "      <th>Kidney Beans</th>\n",
       "      <th>Milk</th>\n",
       "      <th>Nutmeg</th>\n",
       "      <th>Onion</th>\n",
       "      <th>Unicorn</th>\n",
       "      <th>Yogurt</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "      <td>True</td>\n",
       "      <td>False</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Apple   Corn   Dill   Eggs  Ice cream  Kidney Beans   Milk  Nutmeg  Onion  \\\n",
       "0  False  False  False   True      False          True   True    True   True   \n",
       "1  False  False   True   True      False          True  False    True   True   \n",
       "2   True  False  False   True      False          True   True   False  False   \n",
       "3  False   True  False  False      False          True   True   False  False   \n",
       "4  False   True  False   True       True          True  False   False   True   \n",
       "\n",
       "   Unicorn  Yogurt  \n",
       "0    False    True  \n",
       "1    False    True  \n",
       "2    False   False  \n",
       "3     True    True  \n",
       "4    False   False  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "from mlxtend.preprocessing import TransactionEncoder\n",
    "\n",
    "te = TransactionEncoder()\n",
    "te_ary = te.fit(dataset).transform(dataset)\n",
    "df = pd.DataFrame(te_ary, columns=te.columns_)\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let us return the items and itemsets with at least 60% support:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>support</th>\n",
       "      <th>itemsets</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(5, 6)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(8, 3, 5)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(10, 5)</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   support   itemsets\n",
       "0      0.6     (5, 6)\n",
       "1      0.6  (8, 3, 5)\n",
       "2      0.6    (10, 5)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from mlxtend.frequent_patterns import fpmax\n",
    "\n",
    "fpmax(df, min_support=0.6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, `fpmax` returns the column indices of the items, which may be useful in downstream operations such as association rule mining. For better readability, we can set `use_colnames=True` to convert these integer values into the respective item names: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>support</th>\n",
       "      <th>itemsets</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(Kidney Beans, Milk)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(Eggs, Onion, Kidney Beans)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0.6</td>\n",
       "      <td>(Yogurt, Kidney Beans)</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   support                     itemsets\n",
       "0      0.6         (Kidney Beans, Milk)\n",
       "1      0.6  (Eggs, Onion, Kidney Beans)\n",
       "2      0.6       (Yogurt, Kidney Beans)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fpmax(df, min_support=0.6, use_colnames=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More Examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please note that since the `fpmax` function is a drop-in replacement for `fpgrowth` and `apriori`, it comes with the same set of function arguments and return arguments. Thus, for more examples, please see the [`apriori`](./apriori.md) documentation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## API"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "## fpmax\n",
      "\n",
      "*fpmax(df, min_support=0.5, use_colnames=False, max_len=None, verbose=0)*\n",
      "\n",
      "Get maximal frequent itemsets from a one-hot DataFrame\n",
      "\n",
      "**Parameters**\n",
      "\n",
      "- `df` : pandas DataFrame or pandas SparseDataFrame\n",
      "\n",
      "    pandas DataFrame the encoded format.\n",
      "    The allowed values are either 0/1 or True/False.\n",
      "    For example,\n",
      "\n",
      "```\n",
      "    Apple  Bananas  Beer  Chicken  Milk  Rice\n",
      "    0      1        0     1        1     0     1\n",
      "    1      1        0     1        0     0     1\n",
      "    2      1        0     1        0     0     0\n",
      "    3      1        1     0        0     0     0\n",
      "    4      0        0     1        1     1     1\n",
      "    5      0        0     1        0     1     1\n",
      "    6      0        0     1        0     1     0\n",
      "    7      1        1     0        0     0     0\n",
      "```\n",
      "\n",
      "\n",
      "- `min_support` : float (default: 0.5)\n",
      "\n",
      "    A float between 0 and 1 for minimum support of the itemsets returned.\n",
      "    The support is computed as the fraction\n",
      "    transactions_where_item(s)_occur / total_transactions.\n",
      "\n",
      "\n",
      "- `use_colnames` : bool (default: False)\n",
      "\n",
      "    If true, uses the DataFrames' column names in the returned DataFrame\n",
      "    instead of column indices.\n",
      "\n",
      "\n",
      "- `max_len` : int (default: None)\n",
      "\n",
      "    Given the set of all maximal itemsets,\n",
      "    return those that are less than `max_len`. If `None` (default) all\n",
      "    possible itemsets lengths are evaluated.\n",
      "\n",
      "\n",
      "- `verbose` : int (default: 0)\n",
      "\n",
      "    Shows the stages of conditional tree generation.\n",
      "\n",
      "**Returns**\n",
      "\n",
      "pandas DataFrame with columns ['support', 'itemsets'] of all maximal\n",
      "    itemsets that are >= `min_support` and < than `max_len`\n",
      "    (if `max_len` is not None).\n",
      "    Each itemset in the 'itemsets' column is of type `frozenset`,\n",
      "    which is a Python built-in type that behaves similarly to\n",
      "    sets except that it is immutable\n",
      "    (For more info, see\n",
      "    https://docs.python.org/3.6/library/stdtypes.html#frozenset).\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "with open('../../api_modules/mlxtend.frequent_patterns/fpmax.md', 'r') as f:\n",
    "    print(f.read())"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
